// 线性筛法 - 更直观版本
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 5100;
// 埃氏筛：一个合数会被所有质因数筛除（重复标记）
// 欧拉筛：每个合数只被最小质因数筛除一次（无重复）

vector<int> linear_sieve(int n) {
  vector<int> min_prime_factor(n + 1, 0); // 记录每个数的最小质因数
  vector<int> primes;                     // 存储所有质数

  for (int i = 2; i <= n; i++) {

    /*
    如果 min_prime_factor[i] == 0，说明之前没有任何数能筛除 i（即没有比 i
小的质数能整除 i） 这表明 i 没有比它小的因数，因此 i 必定是质数 于是将
min_prime_factor[i] 设为 i（记录其最小质因数是自身），并将 i 加入质数列表

    */
    if (min_prime_factor[i] == 0) { // i是质数
      min_prime_factor[i] = i;
      primes.push_back( i);
    }

    // 用当前质数筛掉i的倍数
    // 用当前数i乘以所有已知质数p，直到p大于i的最小质因数或者p*i大于n。
    for (int p : primes) {
      if (p > min_prime_factor[i] || i * p > n)
        break;
      min_prime_factor[i * p] = p;
    }
  }
  return primes;
}

int main() {
  int n = 100;
  auto primes = linear_sieve(n);

  // 输出所有质数
  for (int p : primes) {
    cout << p << endl;
  }

  return 0;
}